package leetcode.code0108;

import leetcode.helper.tree.TreeNode;

public class Solution1 extends Solution108 {

	public interface Handle {
		public void connect(TreeNode root, TreeNode tn);
	}

	@Override
	public TreeNode sortedArrayToBST(int[] nums) {
		int mid = (nums.length - 1) >> 1;
		TreeNode root = new TreeNode(nums[mid]);
		this.sortedArray(root, nums, 0, mid - 1,(rt,ch)->{rt.left = ch;});
		this.sortedArray(root, nums, mid + 1, nums.length - 1,(rt,ch)->{rt.right = ch;});
		return root;
	}

	private void sortedArray(TreeNode root, int[] nums, int l, int r, Handle handle) {
		if (l > r) {
			return;
		}
		if (l == r) {
			handle.connect(root, new TreeNode(nums[l]));
		}
		int mid = ((r - l) >> 1) + l;
		TreeNode tn = new TreeNode(nums[mid]);
		handle.connect(root, tn);
		this.sortedArray(tn, nums, l, mid - 1,(rt,ch)->{rt.left = ch;});
		this.sortedArray(tn, nums, mid + 1, r,(rt,ch)->{rt.right = ch;});
	}

	private void sortedArrayLeft(TreeNode root, int[] nums, int l, int r) {
		if (l > r) {
			return;
		}
		if (l == r) {
			root.left = new TreeNode(nums[l]);
		}
		int mid = ((r - l) >> 1) + l;
		TreeNode tn = new TreeNode(nums[mid]);
		root.left = tn;
		this.sortedArrayLeft(tn, nums, l, mid - 1);
		this.sortedArrayRight(tn, nums, mid + 1, r);
	}

	private void sortedArrayRight(TreeNode root, int[] nums, int l, int r) {
		if (l > r) {
			return;
		}
		if (l == r) {
			root.right = new TreeNode(nums[l]);
		}
		int mid = ((r - l) >> 1) + l;
		TreeNode tn = new TreeNode(nums[mid]);
		root.right = tn;
		this.sortedArrayLeft(tn, nums, l, mid - 1);
		this.sortedArrayRight(tn, nums, mid + 1, r);
	}

	public static void main(String[] args) {
		System.out.println(1 >> 1);
	}

}
